#include <cstdio>
#include <cstdlib>
#include <queue>

using namespace std;

int cmpfunc(const void* left, const void* right)
{
	int* leftdata = (int*)left;
	int* rightdata = (int*)right;

	return *rightdata - *leftdata;
}
void FindKthLargestNumber1(int* data, int len, int k)
{
	int num = 0;
	int* key = (int*)malloc(sizeof(int) * (k+1));
	for (int i = 0; i < len; ++i)
	{
		key[num++] = data[i];
		if (num > k)
		{
			qsort(key, sizeof(key[0]), num, cmpfunc);
			num--;
		}
	}

	for (int i = 0; i < num; ++i)
	{
		printf("%d,", key[i]);
	}
	printf("\n");
}

void FindKthLargestNumber2(int* data, int len, int k)
{
	int num = 0;
	priority_queue<int,vector<int>, less<int> > key;
	for (int i = 0; i < len; ++i)
	{
		if (num < k)
		{
			num++;
			key.push(data[i]);
		}
		else if (data[i] > key.top())
		{
			key.pop();
			key.push(data[i]);
		}
	}
	while(!key.empty())
	{
		printf("%d,", key.top());
		key.pop();
	}
	printf("\n");
}

void FindTheKthLargestNumber(int* data, int len, int k)
{
	// func 1
	//sort(data, data + len, greater<int>());

	// func 2
	//for (size_t i = 0; i < k; i++)
	//{
	//	int large_pos = i;
	//	for (size_t j = i + 1; j < len; j++)
	//	{
	//		if (data[j] > data[large_pos])
	//		{
	//			large_pos = j;
	//		}
	//		swap(data[large_pos], data[i]);
	//	}
	//}

	// func3
	int ret = -1;
	int l = 0, r = len - 1;
	while (l <= r)
	{
		int area = r - l;
		if (area == k)
		{
			ret = l;
			break;
		}
		else if (area > k)
		{
			int mid = len / 2;
		}
		else
		{
			r -= k;
		}
	}

	//printf("the k th is %d\n", data[k - 1]);
}

int main(int argc, char **argv)
{
	int data[] = {1,5,10,12,6,4,2,16,3,8,7,11,19};
	FindKthLargestNumber1(data, sizeof(data)/sizeof(data[0]), 3);
	FindTheKthLargestNumber(data, sizeof(data) / sizeof(data[0]), 3);
	return 0;
}